package com.itheima.datastructure.binarysearchtree;

import javax.management.ObjectName;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/*
二叉搜索树
 */
public class BSTTree1 {
    BSTNode root;//根节点
    //节点
    static class BSTNode{
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key) {
            this.key=key;
        }
        public BSTNode(int key,Object value){
            this.key=key;
            this.value=value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    //查找关键字对应的值:伪递归实现（return的是方法）。可以考虑改为非递归优化效率
    /*public Object get(int key){
        return doGet(root,key);
    }

    private Object doGet(BSTNode node,int key){
        if(node==null){
            return null; //没找到
        }
        if(key<node.key){
            return doGet(node.left,key); //继续向左找
        }else if(key>node.key){
            return doGet(node.right,key);//继续向右找
        }else{
            return node.value;//找到了
        }
    }*/

    //查找关键字对应的值，非递归实现
    public Object get(int key){
        BSTNode node=root;
        while(node!=null){
            if(key<node.key){
                node=node.left;
            }else if(key>node.key){
                node=node.right;
            }else{
                return node.value;
            }
        }
        return null;
    }

    //查找最小关键字的对应值
    /*public Object min(){
        return doMin(root);
    }*/
    private Object doMin(BSTNode node){
        if(node==null){
            return null;
        }
        if(node.left==null){
            return node.value; //最小的节点
        }
        return doMin(node.left);
    }

    public Object min(){
        return min(root);
    }
    private Object min(BSTNode node){
        if(node==null){
            return null;
        }
        BSTNode p=node;
        while(p.left!=null){
            p=p.left;
        }
        return p.value;
    }


    //查找最大关键字的对应值
    public Object max(){
        return max(root);
    }

    private Object max(BSTNode node){
        if(node==null){
            return null;
        }
        BSTNode p=node;
        while(p.right!=null){
            p=p.right;
        }
        return p.value;
    }

    //添加元素
    public void put(int key,Object value){
        BSTNode node=root;//根节点
        BSTNode parent=null;//要新添加节点的父节点
        while(node!=null){
            parent=node;
            if(key<node.key){
                node=node.left;
            }else if(node.key<key){
                node.right=node;
            }else{
                //1.key本身存在，更新值
                node.value=key;
                return;
            }
        }
        //2.根节点为null
        if(parent==null){
            root=new BSTNode(key,value);
            return;
        }

        //3.key本身存在
        if(key< parent.key){
            parent.left=new BSTNode(key,value);
        }else if(key> parent.key){
            parent.right=new BSTNode(key,value);
        }
    }

    //寻找前驱值
    public Object predecessor(int key){
        BSTNode p=root;//从根节点开始找
        BSTNode ancestorFromLeft=null;//祖先节点
        while(p!=null){
            if(key<p.key){
                p=p.left;
            }else if(key>p.key){
                //记录自左而来的祖先
                ancestorFromLeft=p;
                p=p.right;
            }else{
                break;
            }
        }

        //没有找到就没有前驱
        if(p==null){
            return null;
        }

        //情况1；当前节点有左子树，就找到左子树的最大节点
        if(p.left!=null){
            return max(p.left);
        }
        //情况2：节点如果没有左子树，就寻找离他最近的自左而来的祖先节点
        return ancestorFromLeft!=null?
                ancestorFromLeft.value:null;
    }

    //寻找后继值
    public Object succseeor(int key){
        BSTNode p=root;
        BSTNode ancestorFromRight=null;//自右而来的祖先节点
        while(p!=null){
            if(key<p.key){
                ancestorFromRight=p;
                p=p.left;
            }else if (key>p.key){
                p=p.right;
            }else{
                break;
            }
        }
        //没有找到节点
        if(p==null){
            return null;
        }
        //情况1：节点有右子树，返回左子树的最小值
        if(p.right!=null){
            return min(p.right);
        }
        //情况2：节点没有右子树，离他最近的自右而来的祖先节点
        return ancestorFromRight!=null?
                ancestorFromRight.value:null;
    }

    //根据关键字删除节点
    /*public Object delete(int key){
        BSTNode p=root;
        BSTNode parent=null;//父节点
        while(p!=null){
            if(key<p.key){
                parent=p;
                p=p.left;
            }else if(key>p.key){
                parent=p;
                p=p.right;
            }else{
                break;
            }
        }
        //没有找到
        if(p==null){
            return null;
        }
        //删除操作
        if(p.left==null && p.right!=null){
            //1.情况1,被删除节点没有左孩子，将右孩子托孤给父节点
            shift(parent,p,p.right);
        }else if(p.right==null && p.left!=null){
            //2.情况2,被删除节点没有右孩子，将左孩子托孤给父节点
            shift(parent,p,p.left);
        }else{
            //情况4：
            //被删除节点的后继
            BSTNode s=p.right;
            BSTNode sParent=p;//后继节点的父节点
            while(s.left!=null){
                sParent=s;
                s=s.left;
            }
            //后继节点与删除节点不相邻，就要处理后继节点的后事
            if(sParent!=p){
                shift(sParent,s,s.right);//不可能有左孩子
                s.right=p.right;
            }
            //后继节点取代被删除节点
            shift(parent,p,s);
            s.left=p.right;
        }
        return p.value;
    }*/

    /*
    托孤方法
     */
    private void shift(BSTNode parent,BSTNode deleted,BSTNode child){
        //如果被删除节点是根节点
        if(parent==null){
            root=child;
        }else if(deleted==parent.left){
            parent.left=child;
        }else{
            parent.right=child;
        }
    }

    //递归方法
    public Object delete(int key){
        //保存被删除的值
        ArrayList<Object> result=new ArrayList<>();
        root=doDelete(root, key,result);
        return result.isEmpty()?null:result.get(0);
    }
    /*
    node:开始遍历的起点
    返回被删除节点的子孩子们
     */
    private BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result){
        if(node==null){
            return null;
        }
        if(key<node.key){
            node.left=doDelete(node.left,key,result);
            return node;
        }
        if(key>node.key){
            node.right=doDelete(node.right,key,result);
            return node;
        }
        result.add(node.value);
        //情况1：只有右孩子
        if(node.left==null){
            return node.right;
        }
        //情况2：只有左孩子
        if(node.right==null){
            return node.left;
        }
        //情况3：有两个孩子
        BSTNode s=node.right;
        while(s.left!=null){
            s=s.left;
        }
        //如果不相邻，先把自己给删了
        s.right=doDelete(node.right,s.key,new ArrayList<>());
        s.left=node.left;
        return s;
    }

    //找到<key的所有的value
    public List<Object> less(int key){
        //本质是一个中序遍历，排好序的
        ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else{
                BSTNode pop=stack.pop();
                //处理值
                if(pop.key<key){
                    result.add(p.value);
                }else{
                    break;
                }
                p=pop.right;
            }
        }
        return result;
    }

    public List<Object> greater(int key){
        //本质是一个中序遍历，排好序的
        /*ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else{
                BSTNode pop=stack.pop();
                if (pop.key>key){
                    result.add(pop.value);
                }
                p=pop.right;
            }
        }
        return result;*/
        //反向中序遍历
        ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.right;
            }else{
                BSTNode pop=stack.pop();
                //处理值
                if(pop.key>key){
                    result.add(pop.value);
                }else{
                    break;
                }
                p=p.left;
            }
        }
        return result;
    }

    public List<Object> between(int key1,int key2){
        //本质是一个中序遍历，排好序的
        ArrayList<Object> result=new ArrayList<>();
        BSTNode p=root;
        LinkedList<BSTNode> stack=new LinkedList<>();
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else{
                BSTNode pop=stack.pop();
                //处理值
                if(pop.key>=key1 && pop.key<=key2){
                    result.add(p.value);
                }else if(pop.key>key2){
                    break;
                }
                p=pop.right;
            }
        }
        return result;
    }
}
